/*
 * BigInteger.h
 *
 *  Created on: 2010-3-11
 *      Author: liheyuan
 *    Describe: 实现了大数运算
 *
 *   Last Date: 2010-3-11
 *   CopyRight: 2010 @ ICT LiHeyuan
 */
#ifndef BIGINTEGER_H_
#define BIGINTEGER_H_
#include <stdint.h>
#include <string>
using std::string;

#define MAX_LEN 2048
#define UNIT_WEI 18//最高比UNIT_TYPE能支持的少2，避开符号问题
#define UNIT_MAX_NUM 999999999999999999ll
#define UNIT_JIN_DIFF (UNIT_MAX_NUM+1)
#define UNITS (MAX_LEN/UNIT_WEI)+1
#define UNIT_TYPE uint64_t

#define PRIME_1000_NUMS 168

class BigInteger
{
public:

	virtual ~BigInteger();

	//"0"构造
	BigInteger();
	//根据字符串构造
	BigInteger(string str);
	//小于一个chunk
	BigInteger(UNIT_TYPE num);

	//初始化所有chunk为0
	void initZero();
	//返回长度
	long size() const;
	//返回成string
	string toString() const;
	//返回大数的第几位（从个位为0）
	int getAt(long i) const;
	//返回绝对值
	BigInteger getAbs() const;
	//返回相反数
	BigInteger getNegitive() const;
	//判断是否是'0'
	bool isZero() const;
	//随机生成整数
	static BigInteger getRandomBigInteger(unsigned int n);

	//加法
	BigInteger operator +(const BigInteger &right) const;
	//减法
	BigInteger operator -(const BigInteger &right) const;
	//乘法(加法模拟)
	BigInteger operator *(int right) const;
	//乘法
	BigInteger operator *(const BigInteger &right) const;
	//除法
	BigInteger operator /(const BigInteger &right) const;
	//模小数的余数
	UNIT_TYPE operator %(const UNIT_TYPE &right) const;
	//模小数的余数
	BigInteger operator %(const BigInteger &right) const;
	//慢速模，只使用减法
	BigInteger slowMod(const BigInteger &right) const;

	//计算除法结果和余数
	void
	divAndMod(const BigInteger &right, BigInteger &chu, BigInteger &yu) const;
	//绝对值差大小，左大返回>0，右大返回<0，相等0
	int absDiff(const BigInteger &right) const;
	//小于号
	bool operator <(const BigInteger &right) const;
	//大于号
	bool operator >(const BigInteger &right) const;
	//大于号
	bool operator >=(const BigInteger &right) const;
	//等于号
	bool operator ==(const BigInteger &right) const;

	//是否是奇数
	bool isOdd() const;

	//最大公约数
	BigInteger gcd(const BigInteger &right);
	//判断是否可能是素数
	bool isProbalePrime();
	//快速除2
	BigInteger div2();
	//使用蒙格马利实现模幂乘a^e mod m,快速计算
	BigInteger modPow(BigInteger e, BigInteger m);

private:
	bool smallPrimeTest();
	bool millerRabinTest();

private:

	/**数据区，每个表示PER_WEI个数位*/
	UNIT_TYPE _data[UNITS];//每一个ulong使用PER_WEI个“位数”

	/**符号*/
	bool _sign;//true为正，false为负

	/**最高有效快,0下标*/
	long _maxchunk;

};

#endif /* BIGINTEGER_H_ */
